#include "CompressHuffman.h"
#include "stdio.h"
#include "windows.h"



CompressHuffman::CompressHuffman(void)
{
	size=0;
}

unsigned char *CompressHuffman::ReadFile(char* path) //read file source and copy data to (char *sourcefile)
{
	
	FILE *file=fopen(path,"rb");
	if(!file) return NULL;
	
	//get size of file
	fseek(file,0L,SEEK_END);
	size=ftell(file);
	fseek(file,0L,0);

	unsigned char*sourcefile=new unsigned char[size];
		
	fread(sourcefile,1,size,file);
	fclose(file);
	
	return sourcefile;
}
Node *CompressHuffman::BuildHufftree(Node *huffman,int  &position_node)
{
	int min=10;
	int j=0;
	int position_min1=0,position_min2=0;

	while(true)
	{
		min=10;
		for(int i=0;i<512;i++)
		{
			if(huffman[i].used==false && huffman[i].freg<min && huffman[i].freg>0)
			{
					min=huffman[i].freg;
					position_min1=i;	
			}
		}
		huffman[position_min1].used=true;

		min=10;
		for(int i=0;i<512;i++)
		{
			if(huffman[i].used==false && huffman[i].freg<min && huffman[i].freg>0)
			{

				min=huffman[i].freg;
				position_min2=i;	
				if(huffman[position_node-1].freg<=huffman[position_min2].freg && huffman[position_node-1].freg>0)
				{
						position_min2=position_node-1;
				}
			}
		}
		huffman[position_min2].used=true;
		
		if(position_min1 ==0||position_min2==0) break;

		huffman[position_node].freg=huffman[position_min1].freg+huffman[position_min2].freg; //create node in huffman tree
		huffman[position_node].nleft=position_min1;
		huffman[position_node].nright=position_min2;

		position_min1=0;
		position_min2=0;

		position_node++;
		j++;
	}
	return huffman;
}

bool CompressHuffman::Compress(char* path)
{
	int j=0,i=0,t=0;
	int min=10;
	int position_min1=0,position_min2=0;
	int position_node=256;
	int position_character=0;
	int count=0;
	unsigned char temp_character=0;

	Node *huffman=new Node[512];

	unsigned char *sourcefile=ReadFile(path);
	
	FILE *file=fopen("Compress","wb");
	if(!file) exit(1);

	//Create statistic table
	while(j<size) 
	{
		 huffman[sourcefile[j]].freg++;
		j++;
	}

	j=0;

	//build hufftree to compress
	huffman=BuildHufftree(huffman,position_node);

	//create huffman bit and compress

	j=0;
	while(true) 
	{
		
		for(i=position_node-1;i>255;i--)
		{
			if(sourcefile[j]==huffman[i].nleft||sourcefile[j]==huffman[i].nright) 
				{
					position_character=i;
					break;
				}	
		}

		i=position_node-1;
		while(i>=position_character)
		{
			if(count>7)
			{
				putc(temp_character,file);
				count=0;
				temp_character=0;
			}
			if(i==position_character) 
			{
				if(huffman[position_character].nleft==sourcefile[j]) 
				{
					count++;
					temp_character=temp_character << 1;
					break;
				}
				else 
					if (huffman[position_character].nright==sourcefile[j]) 
					{
						count++; 
						if(count>0) 
							temp_character=temp_character << 1;
						temp_character=temp_character | (1 << 0);
						break;

					}
				}

			if(huffman[i].nleft==position_character||huffman[i].nright==position_character 
			   && huffman[position_node-1].nleft!=position_character && huffman[position_node-1].nright!=position_character)
			{
				if(huffman[position_node-1].nleft==i) 
					{
						temp_character= (temp_character << 1);
						count++;
					}
					else if(huffman[position_node-1].nright==i)
					{
						if(count>0) temp_character=temp_character << 1;
						temp_character=temp_character | (1 << 0);
						count++;
					}
			}	
				
			if(huffman[i].nright==position_character)
			{
				if(count>0) temp_character=temp_character << 1;
				temp_character=temp_character | (1 << 0);
				count++;
			}
			else if(huffman[i].nleft==position_character)
			{
				if(count==0) count++;
				else
				{
					temp_character= (temp_character << 1);
					count++;
				}
			}
		
			i--;
		}

		if( j==size-1)
		{
			putc(temp_character,file);
		}
		j++;
		if(j>=size) break;
		
	}
	fclose(file);

	//write infomation to extract file
	file=fopen("InfomationCompress","wb");
	if(file)
	{
		for(int i=0;i<256;i++)
		{
			if(huffman[i].freg>0)
			{
					putc(i,file);
					putc(huffman[i].freg,file);
					putc(32,file);	
			}
		}
	}
	fclose(file);

	delete []sourcefile;
	delete []huffman;
	huffman=NULL;
	sourcefile=NULL;

	return true;
}

bool CompressHuffman::Extract(char* pathsource,char* pathdest,char* pathinfo)
{
	int j=0,i=0;
	int min=10;
	int position_min1=0,position_min2=0;
	int position_node=256;
	int sizeofsource=0;
	int position_character=0;
	int count=0;

	unsigned char* destfile=ReadFile(pathsource);
	int sizeofcompress=size;
	unsigned char* info_compress=ReadFile(pathinfo);

	FILE *file=fopen("Source","wb");
	if(!file) return false;

	Node *hufftree=new Node[512];

	//build hufftree from infomation compress to Extract
	while(j<size)
	{
		if(info_compress[j]==32) 
		{
				hufftree[info_compress[j-2]].freg=info_compress[j-1];
				sizeofsource=info_compress[j-1]+sizeofsource;
		}
		j++;
	}

	hufftree=BuildHufftree(hufftree,position_node);

	//Extract
	j=0;
	i=position_node-1;
	while(true)
	{
		int k=7;
		while(k<=7&& k>=0)
		{
			int temp=(destfile[j]>>k) & 1;

			
			if(temp==1)
			{
				i=hufftree[i].nright;
			}
			else 
				i=hufftree[i].nleft;
			
			if(i<256 ) 
			{
					putc(i,file);
					i=position_node-1;
					count++;
			}
			k--;
			
			if(count>=sizeofsource) break;
		}
		j++;

		if(j>=sizeofcompress) break;
	}
	fclose(file);

	delete []destfile;
	delete []hufftree;
	delete []info_compress;
	info_compress=NULL;
	hufftree=NULL;
	destfile=NULL;

	return true;
	
}
CompressHuffman::~CompressHuffman(void)
{

}
